# -*- coding:utf-8 -*-

from base.ListNode import ListNode

"""
LeetCode 21: Merge Two Sorted Lists
 考察点：链表的基本操作
 递归的实现方法
 l1: 2 -> 4 -> 9
 l2: 1 -> 3 -> 5
 l1 和 l2 merge:
 2 > 1 :
   l2 > 1 ->
     2 -> 4 -> 9 和  3 -> 5 继续 merge:
     2 < 3 :
   2 ->
     4 -> 9 和 3 -> 5继续merge：
     4 > 3 :
   3 ->
     4 -> 9 和 5 继续merge：
     4 < 5:
   4 ->
      9 和 5 继续merge：
      9 < 5:
   5 ->
      有一链表为已为空，当前next就指向另一非空链表
   9
   返回l2
"""
class MergeTwoLists:
    def mergeTwoLists(self,l1,l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l1 and l2:
            if l1.val > l2.val:
                l2.next = self.mergeTwoLists(l1,l2.next)
                return l2
            else:
                l1.next = self.mergeTwoLists(l1.next,l2)
                return l1
        else:
            return l2 if l2 else l1